<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<META NAME="generator" CONTENT="http://txt2tags.sf.net">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8 !style: owr.css">
<TITLE>DES 加密算法 </TITLE>

<!-- Included owr.css -->
<STYLE TYPE="text/css">
/* 
   Formatting for the txt2tags site
   http://txt2tags.sf.net
   
   Author: Aurelio Marinho Jargas
   http://aurelio.net
   
   License: Public Domain
*/



/***************************** GLOBAL **************************** 
/ Here are the global rules, used everywhere on the page. */
body
	{
	background-color: white;
	color		: #444;
	margin		: 0;
	padding		: 0;
	font-family	: sans-serif;
	overflow	: scroll;  /* Avoids dancing menu */
	overflow-x	: auto; /* IE: horizontal bar is sooo large */
	}

/* Links are underlined only when the cursor is over them */
a
	{
	text-decoration	: none;
	}
a:link
	{
	color		: blue;
	font-weight	: bold;
	}
a:hover
	{
	text-decoration	: underline;
	background 		: #ccf;
	}
a:visited
	{
	color		: #66f;
	}

/* That nice green background on some words and code samples */
code
	{
	background-color: #eee;
	border		: 1px dotted #ddd;
	}
pre
	{
	background-color: #eee;
	margin-left	: 3em;
	margin-right	: 2em;
	padding		: 8px;
	border		: 1px outset gray;
	}

/* Tables are used by: docs, sample */
table
	{
	font-size	: 100%; /* Needed to inherit the body font size*/
	border-color	: #ccc;
	}
th
	{
	background-color: #ddd;
	padding		: .5em 0;
	border-color	: #ccc;
	border-style	: solid;
	}
td
	{
	border-style	: none;
	padding		: .2em .5em;
	}

form
	{
	margin-bottom	: 2em;
	}

/* Mark the tooltip'ed texts (underline and highlight) */
span.tooltip
	{
	border-bottom	: 1px dashed #444;
	}
span.tooltip:hover
	{
	background-color: #cf9;
	}
a.donate
	{
	font-size	: smaller;
	text-align	: center;
	margin		: 0;
	padding		: 0;
	}

/***************************** HEADERS **************************** 
/ Remember that headers are the first three lines of the source file.
/ They are placed inside the #header DIV when using --css-suggar.
/ So we can format it freely without messing other rules.
/
/ Yes, it is that green strip at the top. Note that the white gems
/ image is referred as background.
*/

#header
	{
	background	: #6c6 url(img/t2tgems.png) no-repeat right;
	color		: white;
	margin		: 0;
	padding		: 1em;
	}
#header *
	{
	margin		: 0;
	}
#header h3
	{
	font-weight	: normal;
	}


/***************************** CONTENT **************************** 
/ The page contents are placed inside the #body DIV when using
/ the --css-suggar option. Don't confuse it with the <body> tag.
/ I know it would be better to call it #content, but... too late.
/
/ Inside #body there are the sidebar and the page contents. The
/ sidebar has its own DIV, but the contents doesn't. I could have
/ made an extra DIV for it, but it is not strictly necessary. So
/ some special care is needed to format both using the same container.
*/

#body
	{
	margin		: 0;
	padding		: 0 2em 2em 2em;
	border-top	: 1px solid #6c6; /* Required: Fixes spacing bug */
	line-height	: 130%;
	font-size	: 90%;
	_font-size	: 80%; /* IE: Font becomes ugly with 90% */
	}

/* Normal text is gray, bold is black */
#body b
	{
	font-weight	: normal;
	color		: black;
	}

#body h1
	{
	margin-top	: 1.5em;
	}
#body h2
	{
	padding-top	: 1em;
	color		: #999;
	font-size	: 150%;
	font-weight	: normal;
	}


/***************************** SIDEBAR **************************** 
/ The sidebar is a DIV made "by hand", inserting custom HTML code
/ on the page with %!postproc filters.
/
/ Yes, it is that green strip at the right with the menu links.
/ This is the most tricky part of the CSS, some magic was necessary.
/
/ The sidebar is floated right with its width set in EMs, so it scales
/ with the text size, not window. Cute.
/
/ The right margin is negative so the sidebar can "escape" the #body
/ box padding and stick with the right border of the window.
/
/ The menu links are defined as block so you can click outside the
/ text and it will work. And they're *always* the same color, visited
/ or not.
/
/ Images are showed as blocks with auto margins, to get centered.
*/

#sidebar
	{
	float		: right;
	width		: 9.5em;
	background-color: #cf9;
	color		: #030;
	border-color	: #fff;
	border-style	: solid;
	border-width	: 0 0 1px 1px;
	margin		: 0 -2em 1em 2em;
	padding		: 1em;
	z-index		: 1;
	/* IE: Box model strikes again */
	_width		: 11.5em;
	_margin		: 0 -1em 0 2em;
	}
#sidebar a
	{
	display		: block;
	color		: #363;
	font-weight	: normal;
	}
#sidebar a:hover
	{
	background-color: #ad7;
	}
#sidebar ul {
	margin		: 0 0 0 1em;
	padding		: 0;
}
#sidebar ul li {
	list-style-type	: none;
	_border		: 1px solid #cf9;  /* IE: fixes spaced items bug */
}
#sidebar p
	{
	margin		: 0;
	}
#sidebar img
	{
	display		: block;
	margin		: 1em auto 0 auto;
	_text-align	: center; /* IE: margin:auto didn't work */
	}

/* A special link with the lang ID, placed at the top/right edge */
#sidebar a#lang
	{
	float		: right;
	margin		: -1em -1em 0 0;
	_margin-right	: -.5em; /* IE: well... */
	font-size	: 80%;
	}



/****************************** FOOTER **************************** 
/ Not using footer fixed at the bottom because it is strange.
/ The footer must follow the contents, not the window height.
*/

#footer
	{
	margin		: 3em 0 0 0;
	padding		: .3em;
	border-top	: 1px solid #ccc;
	font-style	: italic;
	_font-style	: normal; /* IE: Italic is ugly */
	font-size	: 80%;
	}
#footer p
	{
	padding		: 0;
	margin		: 0;
	}
#footer a
	{
	font-weight	: normal;
	}
#footer #validate
	{
	float		: right;
	}
#footer img
	{
	float		: right;
	margin-left	: 5px;
	}

/******* Current menu item detection
/
/ Now breath. This is a CSS black magic.
/
/ All pages use a special %!postproc to add an ID to it's <body> tag.
/ All menu items have their own ID also.
/ If we have unique identifiers for pages and menu items, we can
/ combine them to know which is the item for a specific page.
/
/ This is what the following rules do.
/ They add special formatting only for the current page menu item.
/
/ Reading the first: If we're on the #home page, add the bullet
/ for the list item #menuhome, inside the sidebar.
*/

body#home #sidebar li#menuhome,
body#oldnews #sidebar li#menuoldnews,
body#features #sidebar li#menufeatures,
body#sample #sidebar li#menusample,
body#shots #sidebar li#menushots,
body#docs #sidebar li#menudocs,
body#tips #sidebar li#menutips,
body#online #sidebar li#menuonline,
body#markup #sidebar li#menumarkup,
body#download #sidebar li#menudownload,
body#changelog #sidebar li#menuchangelog,
body#tools #sidebar li#menutools,
body#children #sidebar li#menuchildren,
body#comments #sidebar li#menucomments,
body#team #sidebar li#menuteam,
body#ml #sidebar li#menuml,
body#art #sidebar li#menuart
	{
	list-style-type	: square;
	}


/************************** PAGE SPECIFIC ************************* 
/ Since all the pages have an unique ID on <body> tag, we can set
/ specific rules in a breeze, avoiding %!postproc tricks on sources,
/ or multiple tiny CSS files all around.
*/

/* Old News: headlines are bigger and dates are tiny */
body#oldnews dt
	{
	margin-top	: 2em;
	font-size	: 150%;
	color		: #999;
	}
body#oldnews dt i
	{
	font-size	: 60%;
	color		: #aaa;
	}

/* Highlight news about releases */
body#oldnews dd.release
	{
	background-color: #eee;
	border		: 1px solid #ddd;
	color		: #333;
	}

/* Underline is used to mark people names on the Old News */
body#oldnews dd u
	{
	background-color: #eee;
	border		: 1px dotted #ddd;
	text-decoration	: none;
	}

/* Make the flags table smaller, to fit page width */
body#docs td
	{
	padding		: 0;
	}

/* Flags are links, make it clear */
body#docs td img
	{
	border		: 1px solid blue;
	}

/* Highlight the important parts of source code */
body#new-target pre b
	{
	color:red;
	}

/* Avoid pre blocks over sidebar */
body#sample pre,
body#tips pre
	{
	margin-right	: 12em;
	}

/* Increase the contrast to make it more readable */
body#shots h2, body#art h2
	{
	color		: #666;
	}

/* Tips page gets special formatting */
body#tips #body h1
	{
	padding		: 2em 0 1em 0;
	}
body#tips #body h2
	{
	color		: #000;
	font-weight	: bold;
	border-top	: 1px solid #ccc;
	padding-top	: 1.5em;
	padding-bottom	: 1em;
	margin-top	: 1.5em;
	}
body#tips .toc
	{
	margin-top	: 2.5em;
	line-height	: 1.7em;
	}

/* Highlight the catchy terms */
body#features li b
	{
	background-color: #cf9;
	color		: #444;
	}

/* Highlight the "thanks" messages */
body#download li em,
body#changelog li em
	{
	color		: #6c6;
	font-size	: 80%;
	}

/* Back to normal bold */
body#download li b
	{
	font-weight	: bold;
	color		: #444;
	}

/* The sources are preferred */
body#download a.sources
	{
	font-size	: 140%;
	}

/* Markup table is tricky, make it smaller and pretty */
body#markup table
	{
	clear		: right;
	border-spacing	: 0;
	}
body#markup table td
	{
	padding		: 2em 0;
	border-bottom	: 1px solid #ccc;
	}
body#markup table td h1,
body#markup table td h2,
body#markup table td h3
	{
	margin		: 0;
	padding		: 0;
	}
body#markup table td pre
	{
	margin		: 0 1.5em 0 0;
	padding		: 0 .5em 1em .5em;
	}
body#markup table td dt
	{
	font-style	: italic;
	}
body#markup table td table td
	{
	border		: 1px solid #ccc;
	padding		: .5em;
	}

/* The nice testimonials box */
#testimonials
	{
	clear		: right;
	float		: right;
	width		: 18em;
	margin		: 2em 0 0 2em;
	padding		: 1em;
	font-family	: serif;
	color		: #222;
	/* Tried outset, but the colors change on Opera */
	border-top	: 1px solid #ccc;
	border-left	: 1px solid #ccc;
	border-right	: 2px solid #999;
	border-bottom	: 2px solid #999;
	}
/* Brighten the names to improve comments readability */
#testimonials .name
	{
	color		: #999;
	}

#donate .ballon
	{
	background	: #eee url(img/aurelio.jpg) no-repeat bottom left;
	padding		: 2em 82px 1em 82px;
	margin		: 3em 0 2em 1em;
	width		: 20em;
	border		: 5px solid #555;
	}
#donate .ballon p
	{
	font-family	: skia, sans-serif;
	text-align	: center;
	line-height	: 140%;
	}
#donate .ballon p:hover
	{
	color		: black;
	}

/* Splash download button */
body#home img.splashimg
	{
	display		: block;
	margin		: 4em auto;
	text-align	: center;
	}
body#home a:hover img
	{
	outline		: 2px dashed #09f;
	}
</STYLE>

</HEAD><BODY BGCOLOR="white" TEXT="black">
<P ALIGN="center"><CENTER><H1>DES 加密算法 </H1>
<FONT SIZE="4">
<I>owr</I><BR>
10/06/2010
</FONT></CENTER>

<P></P>
<HR NOSHADE SIZE=1>
<P></P>
    <UL>
    <LI><A HREF="#toc1">一. 加密过程简介</A>
    <LI><A HREF="#toc2">二. 详细过程</A>
      <UL>
      <LI><A HREF="#toc3">1. 密钥部分</A>
      <LI><A HREF="#toc4">2. 明文部分</A>
      </UL>
    <LI><A HREF="#toc5">三. 解密过程</A>
    </UL>

<P></P>
<HR NOSHADE SIZE=1>
<P></P>
<A NAME="toc1"></A>
<H2>一. 加密过程简介</H2>
	<BLOCKQUOTE>
	<B>DES 加密算法</B> 的名字直译的话就是数据加密标准，名字够牛的吧。如
	果想了解更多，请八卦文献<B>Processing Standards Publication 46-3</B>
	。这里就不重新发明车轮子了。
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	<B>DES 加密算法</B>的原型是<B>Feistel算法</B>，<B>DES</B> 沿用了<B>Feistel</B>
	的流程。<B>Feistel</B> 是分组加密的，一组 64 位，每组又分成左右(LR)两
	部分。加密的主线就是围绕每个小分组展开的，加密时，每组的左右部分轮
	流加密，一共加密 16 轮，加密前后分别有一次初始置换跟初始逆置换，输
	出加密后的内容，最终完成加密全过程。其解密的过程跟加密过程完全一样
	的（异或的威力，详情请见后文），就是把密钥反过来用，后文将会看到，
	这是有坚实的数学理论依据的。
	</BLOCKQUOTE>
<P></P>
<A NAME="toc2"></A>
<H2>二. 详细过程</H2>
	<BLOCKQUOTE>
	整个加密过程是围绕密钥和跟明文展开的，在 16 轮的加密过程中，每轮加
	密用的密钥都是不同的，所以一共有 16 个子密钥，它们都是由原始密钥生
	成的；每轮加密时，前一轮的输出作为后一轮的输入。密钥处理跟明文处理
	的流程的之间的联系不是很密切，耦合程度不高，所以将它们分开考虑会更
	容易看明白理清楚整个加密算法的流程。
	</BLOCKQUOTE>
<P></P>
<A NAME="toc3"></A>
<H3>1. 密钥部分</H3>
<P>
<B>A. PC-1 置换</B>
</P>
	<BLOCKQUOTE>
	初始提供的密钥是 64 位的，但通过 <B>PC-1 置换</B>，最终给力的只有 56
	位。<B>PC-1 置换</B> 就是在初始的 64 位密钥里抠出 56 位来，这 56 位还
	分开抠，左边(<I>C0</I>) 28 个，右边(<I>D0</I>) 28 个。具体怎么抠，是由
	<B>PC-1 置换矩阵</B> 给定的（说是矩阵，其实就是一个一维的简单交换），
	左右各有一个。
	</BLOCKQUOTE>
<P></P>
<P>
<B>B. 子密钥生成</B>
</P>
	<BLOCKQUOTE>
	完成了 <B>PC-1 置换</B>，得到了 <I>C0</I> 跟 <I>D0</I> 这两个初始子密钥种子
	，注意，它们是<B>种子</B>，还不是密钥。
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	把 <I>C0</I>，<I>D0</I> <B>循环左移</B> <I>n</I> 次，再经过一个 <B>PC-2 置换</B>
	就得到了子密钥 <I>K1</I>。<I>n</I> 是多少，是由数组 <I>R</I> 决定的，<I>R</I>
	数组规定了16 个子密钥生成过程中，每个需要循环左移的位数。那
	<B>PC-2置换</B> 又是干嘛的呢？它是要从左右各 28 位的两个小子密钥中抽
	出 48位，形成一个 48 位的大子密钥。<B>PC-2 置换</B> 保证了抽取过程中
	，左右两边的公平性。这样就生成了子密钥 <I>K1</I>，接着把 <I>K1</I> 作为
	输入，生成 <I>K2</I>，依此类推，直到生成 <I>K16</I>。
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	这里有个小疑问，为什么要抽取的 48 位，而是其它的呢？因为生成的密钥
	要拿来跟明文异或的（见<B>明文部分</B>），待异或的明文是 48 位，所以子
	密钥也要是这么多位才能配得上。
	</BLOCKQUOTE>
<P></P>
<A NAME="toc4"></A>
<H3>2. 明文部分</H3>
<P>
<B>A. 初始置换和逆初始置换</B>
</P>
	<BLOCKQUOTE>
	明文每组的输入是 64 位，在真正的加密函数 F 作用前后，都要进行一次
	<B>初始置换</B>和<B>初始逆置换</B>，说白了，就是先捣乱一下顺序，然后又把
	顺序捣回去，如此折腾的原因，也是为了加强加密效果（对统计分析式的破
	解丝毫不起作用^_^）。
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	初始置换完成后，把 64 位的明文做拆分，拆成左右各 32 位的 L 跟 R。
	假设我们处于第 i 轮的加密过程。给的输入是 <I>Li-1</I>，<I>Ri-1</I> 跟密
	钥 <I>Ki</I>，现在我们要得到输出 <I>Li</I>，<I>Ri</I>。怎么做？下面的公式给
	了我们答案：
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			<I>Li = Ri-1</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			<I>Ri = Li-1 XOR F(Ri-1, Ki)</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	相信很容易看明白，XOR 代表异或，下面来说说函数 F。由上边公式可以看
	出，F 一轮加密过程里，只对明文的右半部分起作用(全盘考虑的话，左右
	交替，就实现了整体加密了)，F 函数完成的顺序功能如下：
		<BLOCKQUOTE>
		<B>扩充置换</B>
			<BLOCKQUOTE>
			将 32 位明文的右(<I>Ri-1</I>)部分用<B>扩展置换 E</B> 将其扩充到
			48 位，其中有 16 位是重复的。
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
		<B>密钥异或</B>
			<BLOCKQUOTE>
			用密钥 <I>Ki</I> 跟上述扩充后的 <I>Ri-1</I> 异或，异或的结果送给
			<I>Ri-1</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
		<B>替换选择</B>
			<BLOCKQUOTE>
			替换选择是整个加密过程的关键之所在，它是整个过程中唯一
			一个不可逆的一个操作，在好多 <B>DES</B> 加密硬件里，这部
			分都是个很神秘的所在。
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			这部分主要完成的功能是替换，完成替换功能的部件叫 S 盒。一
			共有 8 个 S 盒，分别对应 8 组替换，每个 S 都由 4 行16 列构
			成，每个里面填充着一个介于 0-15 之间的某个数。
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			S 盒子具体要完成的功能是把 48 位的输入，经过某种替换，得到
			16 位的输出。它是怎么做到的呢？先把48 位分成 8 组，每组 6 位
			，高低位形成一个 2 位的二进制数，转换成十进制，就对应 S 盒
			的某一行，同理，取中间 4 位，得到该行的某列，这样就得到一
			个数(0-15)，转换成二进制，整好得到 4 位的输出。至此，S 盒
			就完成了它的功能。
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
		<BLOCKQUOTE>
		<B>置换选择</B>
			<BLOCKQUOTE>
			<I>DES</I> 加密算法对经过 <I>S</I> 盒处理过的明文还是不放心
			，于是再它后面又进行了一次置换选择，无非就是把顺序给打
			乱了一下。
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	至此，F 函数完成了它的功能，接着再拿 <I>Li-1</I> 跟 经过 F 处理的
	<I>Ri-1</I> 异或一次，就得到<I>//Ri</I> 。<I>Li</I> 很简单，就是之前未经过
	F 作用的 <I>Ri-1</I>。
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	这就是一整轮的加密过程了，如此加密 16 轮，加密过程便完成了。
	</BLOCKQUOTE>
<P></P>
<A NAME="toc5"></A>
<H2>三. 解密过程</H2>
	<BLOCKQUOTE>
	正如前面说过的，解密过程跟加密是完全一样的，就是密钥用的顺序相反。
	我们来看一下这样做的数学依据：
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	先来看一下异或的特性：
		<BLOCKQUOTE>
		如果 <I>A XOR B = C</I>，那么 <I>A XOR C = B</I>，<I>B XOR C = A</I>。
		相关证明可以在任意一本有关数论的书籍里找到。
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	再由加密过程中的第二个式子，有：
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			<I>Li-1 = Ri XOR F(Ri-1, Ki)</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	又
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			<I>Ri-1 = Li</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	有，
		<BLOCKQUOTE>
			<BLOCKQUOTE>
			<I>Li-1 = Ri XOR F(Li, Ki)</I>
			</BLOCKQUOTE>
		</BLOCKQUOTE>
	</BLOCKQUOTE>
<P></P>
	<BLOCKQUOTE>
	于是 <I>L-i</I> 跟 <I>Ri-1</I> 都得以解出。整个算法的奥妙之所在就是异或
	。
	</BLOCKQUOTE>
<P></P>

<!-- html code generated by txt2tags 2.5 (http://txt2tags.sf.net) -->
<!-- cmdline: txt2tags -t html -\-toc -\-style=owr.css -\-css-inside DES.t2t -->
</BODY></HTML>
